/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ServicioGrafo;

import estructuras.TArista;
import estructuras.TNodo;
import java.io.*;
import java.util.ArrayList;
import java.util.Random;
import java.util.StringTokenizer;

/**
 *
 * @author Karina
 */
public class ServicioGrafo {
    
    private int regresoInicial;
    private int numAristas;
    private int numNodos;
    private int nodoActual;
    private int nodoInicial;
    private int beta,tau,i;
    private int numNodosConectados;
    private int numNodosSeleccionados;
    private double alpha;
    private int distanciaTotal;
    private int todasAristasVisitadas;
    private int contadorAristas;
    private int bestDist;
    private int worstDist;
    
    public void setNodoInicial(int a){
        nodoInicial=a;
    }
    public int getNodoInicial(){
        return nodoInicial;
    }
    public void setContador(int c){
        contadorAristas=c;
    }
    public int getContador(){
        return contadorAristas;
    }
    public void setNumNodos (int valor){
        this.numNodos=valor;
    }
    public int getNumNodos  (){
        return numNodos;
    }
    public void setAlpha (double valor){
        this.alpha=valor;
    }
    public void setDistanciaTotal(int dt){
        this.distanciaTotal=dt;
    }
    
    public int getDistanciaTotal(){
        return this.distanciaTotal;
    }
    /***************************/
    public void firstLn(String linea){
        
        StringTokenizer token = new StringTokenizer(linea," ");
        
        String cad1=token.nextToken();
        String cad2=token.nextToken();
        
        numNodos = Integer.parseInt(cad1);
        numAristas = Integer.parseInt(cad2);
    }
    /***************************/
    public TArista[][] leerArchivoGrafo(String dir) throws IOException{
        
        
        String linea;
        File archivo = new File(dir);
                
        try {
            
            int peso,verticeI,verticeF;
            FileReader fileR = new FileReader(archivo);
            BufferedReader bufferR = new BufferedReader(fileR);
            
            linea=bufferR.readLine();
            //obtener datos de linea inicial
            int nVer=0,nAri=0;
            firstLn(linea); //Aquí actualizamos el numero de nodos y el numero de aristas
            TArista grafo[][]=new TArista[numNodos][numNodos];
            //Inicializamos el grafo como vacio sin conexiones
            for(int k=0; k<numNodos;k++){
                for(int j=0; j<numNodos;j++){
                    grafo[k][j]= new TArista(-1,-1,0);                
                }            
            }
            //Recorremos todo el archivo y rellenamos el grafo
            while ((linea=bufferR.readLine())!=null){
                
                StringTokenizer token = new StringTokenizer(linea," ");
                
                verticeI=Integer.parseInt(token.nextToken());
                verticeF=Integer.parseInt(token.nextToken());
                peso=Integer.parseInt(token.nextToken());
                
                grafo[verticeI][verticeF].setPeso(peso);
            }
            return grafo;
            
        } catch (FileNotFoundException ex) {
           System.err.println("Ocurrio un error en la lectura: " + ex.getMessage());
        } 
        return null;
    }
    
    /***************************/
    public String GeneraCadenaSolucion(ArrayList<Integer> sParcial){
        
       String cadSolucion= "Camino : ";
       
       for(int i=0;i<sParcial.size();i++){
          cadSolucion +=sParcial.get(i)+" ";
       }
       
       cadSolucion += "\nDistancia Total = "+getDistanciaTotal()+"";
       
       return cadSolucion;
    }
    
    /***************************/
    
    public void inicializar( ArrayList<Integer> camino ){

        contadorAristas=0;
        nodoActual = nodoInicial; 
        regresoInicial = 0;        
        numNodosConectados = 0;
        numNodosSeleccionados = 0;
        distanciaTotal = 0;
        todasAristasVisitadas=0;
        camino.clear();
        camino.add(nodoActual);
        
    }
    
    /***************************/
    
    public void conectar(ArrayList<TNodo> nodosConectados,TArista grafo[][] ){
        /*Devolver todos los nodos conectados a ciudadActual */   
        
        int i ; //contador para los bucles        
        //verificar si existe sentido correcto o no
        nodosConectados.clear();
        
        //bucle para revisar la columna
        for(i=0;i<numNodos;i++){
            
            if(i==nodoActual)break;
            
            if((grafo[i][nodoActual].getPeso())!=-1){              
                TNodo aux= new TNodo(); 
                aux.setNodo(i);
                aux.setPeso(grafo[i][nodoActual].getPeso());
                aux.setPrioridad(grafo[i][nodoActual].getSentido());
                nodosConectados.add(aux);
            }
        }
        
       //bucle para revisar la fila  
       for(i=nodoActual+1;i<numNodos;i++){
           
           if (i>numNodos)break; 
           
           if((grafo[nodoActual][i].getPeso())!=-1){
                TNodo aux= new TNodo(); 
                aux.setNodo(i);
                aux.setPeso(grafo[nodoActual][i].getPeso());
                aux.setPrioridad(grafo[i][nodoActual].getSentido());
                nodosConectados.add(aux);
           }
       }
       int minCantVisit;
       
       if(grafo[nodoActual][nodosConectados.get(0).getNodo()].getPeso()==-1)
            minCantVisit=grafo[nodosConectados.get(0).getNodo()][nodoActual].getNumVisitas();
       else
            minCantVisit=grafo[nodoActual][nodosConectados.get(0).getNodo()].getNumVisitas();       
        
       int aux,w;
       
       for (w=0;w<nodosConectados.size();w++){
           
           if(grafo[nodoActual][nodosConectados.get(w).getNodo()].getPeso()==-1)
               aux=grafo[nodosConectados.get(w).getNodo()][nodoActual].getNumVisitas();
           else
               aux=grafo[nodoActual][nodosConectados.get(w).getNodo()].getNumVisitas();
           
           if(aux<minCantVisit)
               minCantVisit=aux;          
       }
       
       for(w=0;w<nodosConectados.size();w++){
           
           if(grafo[nodoActual][nodosConectados.get(w).getNodo()].getPeso()==-1)
               aux=grafo[nodosConectados.get(w).getNodo()][nodoActual].getNumVisitas();
           else
               aux=grafo[nodoActual][nodosConectados.get(w).getNodo()].getNumVisitas();
           if(aux>minCantVisit){
                    nodosConectados.remove(w);w-=1;                       
           }    
       }
       
//       int minPrior=nodosConectados.get(0).getPrioridad();
//       //Determinamos la minima prioridad del camino
//       for (int k=0;k<nodosConectados.size();k++){
//           if(nodosConectados.get(k).getPrioridad()<minPrior){
//               minPrior=nodosConectados.get(k).getPrioridad();
//           }
//       }
//       //Eliminamos de nuestra lista de candidatos aquellos que tengan una prioridad menor
//       for(int k=0;k<nodosConectados.size();k++){
//  
//            if(nodosConectados.get(k).getPrioridad()>minPrior){
//                nodosConectados.remove(k);k-=1;                       
//            }
//    
//       }
       
       //devuelvo la cantidad de nodos conectados
       numNodosConectados =nodosConectados.size();
                
    }    
    
    /***************************/
    
    public void mejor_Peor_Camino(ArrayList<TNodo> nodosConectados){
        
        bestDist    =   nodosConectados.get(0).getPeso();
        worstDist   =   nodosConectados.get(0).getPeso();
        
        for(int i=0;i<numNodosConectados;i++){
            //if (i+1<nodosConectados.size()){
                if(nodosConectados.get(i).getPeso()<bestDist) {
                    bestDist=nodosConectados.get(i).getPeso();
                }
                if(nodosConectados.get(i).getPeso()>worstDist) {
                    worstDist=nodosConectados.get(i).getPeso();
                }                   
            //}
        }
    }    
    /***************************/
    
    public void agregar_al_RCL(ArrayList<TNodo> RCL, ArrayList<TNodo> nodosConectados){
       int min= beta; //asigno minimo
       double max=(double)(beta+alpha*(tau-beta)); //asigno maximo
       
       RCL.clear();
       
       for(int i=0; i<numNodosConectados;i++){ //Se evaluan todos los nodos conectados
            if((nodosConectados.get(i).getPeso() >= min)&&(nodosConectados.get(i).getPeso() <= max)){
                //solo se seleccionan aquellos que están en el rango y se agregan al RCL
                RCL.add(nodosConectados.get(i));               
            }
        }
        
        numNodosSeleccionados = RCL.size();
    }
    
     /***************************/
    public int aleatorio(ArrayList<TNodo> RCL){
      /* aleatorio devuelve la posicion del vertice que se eligio aleatoriamente (OJO: devuelve el indice de grafo, donde
     la arista de vertice inicial ciudadActual y vertice final el que se haya escogido de RCL)*/
    
        Random sacaRandom = new Random();
        int randNum = sacaRandom.nextInt(numNodosSeleccionados);
        int aux = RCL.get(randNum).getNodo();
        
        return aux;
    }
    
    /***************************/
    
    public void actualizarGrafo(TArista grafo[][] ,ArrayList<Integer> camino){
        
        //Se actualizan las aristas en ambos sentidos
        int aux;
        if(grafo[nodoActual][i].getPeso()==-1) {
            aux=grafo[i][nodoActual].getNumVisitas();
            grafo[i][nodoActual].setNumVisitas(grafo[i][nodoActual].getNumVisitas()+1);
           
        }
        else{
            aux=grafo[nodoActual][i].getNumVisitas();
            grafo[nodoActual][i].setNumVisitas(grafo[nodoActual][i].getNumVisitas()+1);            
        }
        
        if(aux==0)
            contadorAristas++;
        //grafo[i][nodoActual].setNumVisitas(grafo[i][nodoActual].getNumVisitas()+1);

        
        //grafo[nodoActual][i].setSentido(grafo[nodoActual][i].getSentido()+1);//Probando
        //grafo[i][nodoActual].setSentido(grafo[i][nodoActual].getSentido()+1);
        
        
        
        camino.add(i);      
    }
    /***************************/
    
    public int calculaTotal(ArrayList<Integer> camino,TArista grafo[][]){
    
        int total=0;
        int x,y,aux;
        for(int g=0;g<camino.size()-1;g++){
            x=camino.get(g);
            y=camino.get(g+1);
            aux=total;
            total+=grafo[x][y].getPeso();
            if(aux>total){
                total+=1+(grafo[y][x].getPeso());
            }
        }
        return total;
    }
    
    /***************************/
    
    public ArrayList<Integer> AlgConstGrasp(TArista grafo[][],ArrayList<Integer> camino, ArrayList<TNodo> nodosConectados){

        
        ArrayList<TNodo> RCL = new ArrayList<>();
        
        inicializar(camino);
        
        while ((todasAristasVisitadas == 0)||(regresoInicial == nodoInicial)){
            
            conectar(nodosConectados,grafo);  
            mejor_Peor_Camino(nodosConectados);
            beta = bestDist;
            tau = worstDist;           
            
            agregar_al_RCL(RCL, nodosConectados);            
            i = aleatorio(RCL);
            
            actualizarGrafo(grafo,camino); 
            //Actualizamos el nodo actual en el nodo elegido
            nodoActual = i;
            
            if (nodoActual == camino.get(0)) {
                regresoInicial = 1;
            }
            else {
                regresoInicial = 0;
            }          
            if(contadorAristas==numAristas)
                todasAristasVisitadas=1;
        }
        
        distanciaTotal=calculaTotal(camino,grafo);
        
        return camino;
    }    
}
